Elliptic curve cryptography has been used for a number of years to provide security against access to confidential information, trade secrets and private communications. For example, two U.S Patents in the name of Mohammad K. Ibrahim, U.S. Pat. Nos. 7,483,533 and 7,483,534 are directed to Elliptic Polynomial Cryptography with Multi X- and Y-Coordinates respectively, embedding. Methods of cryptographic encryption and decryption use more than one quadratic variable that are termed X and Y coordinates. The additional “mx” coordinates and “my” coordinates are used to obtain an elliptic polynomial equation with multi x and y coordinates instead of one x coordinate and one y coordinate. The additional mx coordinates are used to embed extra message data bits.
Any ny-fold increase in the number of embedded message data bits in a single elliptic point can be achieved with the improved method. The reason is that the number of points that satisfy an elliptic polynomial equation defined over F(p) and which can be used in the corresponding cryptosystem is increased by a factor of (#F)mx or ny, where # denotes the size of the field. The use of additional x or y coordinates can then be used to reduce computational complexity. Alternatively, this can be used to increase security by making the bit positions where data bits are embedded known only to the sender and receiver. Also, it can be used as a countermeasure by randomizing the bit positions where data bits are embedded.
A recent U.S. Patent of Nogami et al., U.S. Pat. No. 8,300,808 is directed to an Arithmetic Operation Method and Arithmetic Operation Device. As disclosed, where there exists a plurality of different elements Y and each element Y is represented by tuples in which a plurality of different elements X are combined with an operator, an arithmetic operation method for calculating each element Y by using an electronic computer that associates each element Y with the element X by setting each element X, sets temporary data having an index indicating whether or not each element Y has an identical element X for each element X, and represents each element Y by the temporary data combined with the operator. When there is a combination of temporary data which is common in a plurality of elements Y in temporary data contained in each element Y, new temporary data is set by combining the common temporary data and each element Y consisting of each tuple is calculated using new temporary data.
A more recent U.S. Pat. No. 8,345,864 of Robinson et al. is entitled Elliptic Curve Cryptography Scalar Multiplication With On Demand Acceleration Table Generation. As disclosed, the invention involves dynamic generation of at least a portion of an acceleration table for use in elliptic curve cryptography. Such dynamic generation is capable of providing savings with regard to carrying out elliptic curve cryptography without an acceleration table. Furthermore, once the portion of the acceleration table is dynamically generated and stored in a high speed cache, the portion of the acceleration table is capable of being used on subsequent elliptic curve cryptography operations as well, thus enabling the cost of dynamically generating the acceleration table to be amortized across multiple elliptic curve cryptography operations.
The aforementioned patents are directed primarily to elliptic curve cryptography as opposed to providing security against side channel attacks or simple power analysis attacks. However, two of the literature references listed at the end of this specification are directed to “Timing Attacks on Implementation of Diffie-Hellman, RSA, DSS and Other Systems” by Paul C. Kocher and “Differential Power Analysis” by Paul Kocher, Jasem Jaffe and Benjamin Jun.
The first article points out that computers and microchips leak information about the operations they process and examines specific methods for analyzing power consumption measurements to reveal secret keys from tamper resistant devices. The article also discusses approaches for building crypto systems that can operate securely in existing hardware that leaks information.
The second of the aforementioned articles by Paul Kocher et al. examines specific methods for analyzing power consumption measurements to find secret keys from tamper resistant devices and approaches for building crypto systems that can operate securely in existing hardware that leaks information.
Notwithstanding the above, and because of the physical characteristics of all tamper resistant devices and their use in potentially hostile environments, it is presently believed that there is a need and a potential commercial market for methods and systems for securing elliptic curve cryptography against simple power attacks. The methods in accordance with the present invention are efficient, cost effective and processed using reduced computational time.